package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * ```
 * 1305. 两棵二叉搜索树中的所有元素
 *
 * 给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.

 * 示例 1：
 * 输入：root1 = [2,1,4], root2 = [1,0,3]
 * 输出：[0,1,1,2,3,4]
 *
 * 示例 2：
 * 输入：root1 = [1,null,8], root2 = [8,1]
 * 输出：[1,1,8,8]
 *
 * 提示：
 * 每棵树的节点数在 [0, 5000] 范围内
 * -105 <= Node.val <= 105
 * ```
 */
class leetcode_1305 {
    @Test
    fun test_2() {
        val root1 = TreeNode(1)
        root1.right = TreeNode(8)

        val root2 = TreeNode(8)
        root2.left = TreeNode(1)

        val actual = getAllElements(root1, root2)
        val expected = arrayListOf(1, 1, 8, 8)
        Assert.assertEquals(expected, actual)
    }

    fun getAllElements(root1: TreeNode?, root2: TreeNode?): List<Int> {
        /*
        题型：二叉树的任何一种遍历方式。答案中用的是前序遍历
        思路：
        收集root1 到列表
        收集root2 到列表
        然后排序列表
         */
        val result: ArrayList<Int> = ArrayList()
        collect(root1, result)
        collect(root2, result)
        println(result)
        result.sort()
        println(result)
        return result
    }

    fun collect(root: TreeNode?, result: ArrayList<Int>) {
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        if (null == root) {
            return
        }

        // 3 确认单层递归的处理逻辑:前序遍历
        // 中
        result.add(root.`val`)
        // 左
        collect(root.left, result)
        // 右
        collect(root.right, result)
    }

    fun getAllElements2(root1: TreeNode?, root2: TreeNode?): List<Int> {
        val list: ArrayList<Int> = ArrayList()
        collect(root1, root2, list)
        list.sort()
        return list
    }

    fun collect(root1: TreeNode?, root2: TreeNode?, result: ArrayList<Int>) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root1 && null == root2) {
            return
        }
        // 3 确定单层递归的处理逻辑：前序遍历
        // 中
        if (root1 != null) {
            result.add(root1.`val`)
        }
        if (root2 != null) {
            result.add(root2.`val`)
        }

        collect(root1?.left, root2?.left, result)
        collect(root1?.right, root2?.right, result)
    }
}